package class03

type MyHeap struct {
	nodes []interface{}
	size  int
	index int
	compare func(interface{}, interface{})bool
}

func NewMyHeap(size int, fn func(interface{}, interface{})bool) MyHeap {
	return MyHeap{
		compare: fn,
		nodes: make([]interface{}, size),
		size: size,
		index: 0,
	}
}

func (mh *MyHeap) Insert(node interface{}){
	if mh.index == mh.size {
		panic(any("heap is full！"))
	}
	mh.nodes[mh.index] = node
	parent := (mh.index-1)/2
	cur := mh.index
	for cur > 0 {
		if mh.compare(mh.nodes[cur], mh.nodes[parent]) {
			mh.swap(cur, parent)
		}
		cur = parent
		parent = (cur-1)/2
	}
	mh.index++
}

func (mh *MyHeap) Top() interface{} {
	if mh.index == 0 {
		panic(any("heap is empty！"))
	}
	return mh.nodes[0]
}

func (mh *MyHeap) Poll() interface{} {
	if mh.index == 0 {
		panic(any("heap is empty！"))
	}
	ans := mh.nodes[0]
	mh.swap(0, mh.index-1)
	mh.index--
	mh.heapify(0)
	return ans
}

func (mh *MyHeap) heapify(index int) {
	parent := index
	suitable := (parent<<2) + 1
	for suitable < mh.index {
		if suitable+1 < mh.index && !mh.compare(mh.nodes[suitable], mh.nodes[suitable+1]) {
			suitable = suitable+1
		}
		if mh.compare(mh.nodes[suitable], mh.nodes[parent]) {
			mh.swap(suitable, parent)
		} else {
			break
		}
		parent = suitable
		suitable = (parent<<2) + 1
	}
}

func(mh *MyHeap) swap(index1, index2 int) {
	mh.nodes[index1], mh.nodes[index2] = mh.nodes[index2], mh.nodes[index1]
}

func(mh *MyHeap) Size() int {
	return mh.index
}